/*
 * Creado el 16/11/2011
 */

package fpuna.ia.ea.moaco;

import java.util.Random;
import java.util.Iterator;

import fpuna.ia.ea.FrentePareto;
import fpuna.ia.ea.Punto;
import fpuna.ia.ea.instancia.Instancia;

/**
 *
 * @author gusamasan
 */
public class MOACSQAP {
// -----------------------------------------------------------------------------

    public static int NO_ACCESIBLE  = -1;
    public static int INFINITO      = 10000;

    private double      beta, lambda, qInicial, rho, tInicial, feromanaT[][];

    private double mDistancias[][]  ,
                   mObjetivo1[][]   ,
                   mObjetivo2[][]   ,
                   tau;

    private int         servicioInicio                ,
                        cantidadLocalidades            ,
                        cantidadHormigas            ,
                        cantidadMaximaGeneraciones  ,
                        generacion                  ,
                        indiceActual                ,
                        vectorActual[];


    private Instancia   intanciaProblema;

    private Random      numerSeudoAleatorio;

    private FrentePareto    frentePareto;

    private Punto       nuevoPunto;

// -----------------------------------------------------------------------------

    /** Constructores *********************************************************/
    public MOACSQAP(){
    }
    /**************************************************************************/


    private void actualizarConjuntoPareto(){
    // ----------------------------------------------------------------------

        int indice, vectorSolucion[];

    // ----------------------------------------------------------------------

        vectorSolucion  = new int[ this.cantidadLocalidades ];
        
        for( indice=0; indice < this.cantidadLocalidades; indice++ ){
            vectorSolucion[ indice ] =  this.vectorActual[ indice ];
        }

        this.nuevoPunto.setSolucion( vectorSolucion );
        
        this.frentePareto.agregarSiNoDominado( this.nuevoPunto );
    }

    private void actualizarFeromonasParaCadaSolucion( double productoValoresPromedios ){
    // ------------------------------------------------------------------------

        int indice, i, j, limite, solucion[];

        double tau;

        Iterator puntosFrente;

        Punto   unPunto;

    // ------------------------------------------------------------------------


        puntosFrente = this.frentePareto.obtenerPuntosFrente();

        while( puntosFrente.hasNext() ){

            unPunto     = (Punto)puntosFrente.next();

            solucion    = unPunto.getSolucion();

            i           = this.servicioInicio;
            limite      = this.cantidadLocalidades;

            for( indice= 1; indice < limite; indice++ ){
                j                           = solucion[ indice ];

                tau                         = this.feromanaT[ indice ][ j ];
                tau                         = ( 1 - rho)*tau;
                tau                         = tau + this.rho/productoValoresPromedios;

                this.feromanaT[ indice ][ j ]    = tau;
                
            }

            
        }

    }
    
    private void actualizarFeromonas(){
    // -------------------------------------------------------------------------


        double tPrima, productoValoresPromedios;

    // -------------------------------------------------------------------------

        productoValoresPromedios    = this.frentePareto.obtenerProductoValoresPromedios();

        tPrima                      = 1/productoValoresPromedios;

        if( tPrima > this.tInicial ){
            this.tInicial   = tPrima;

            this.inicializarMatrizFeromonas();
        }
        else{
            this.actualizarFeromonasParaCadaSolucion( productoValoresPromedios );
        }
        
    }

    public void buscarConjuntoPareto(){
    // ------------------------------------------------------------------------

        int hormiga;

    // ------------------------------------------------------ ------------------

        this.inicializarParametros();
        
        while( !condicionParada() ){
            this.generacion++;

            for( hormiga=0; hormiga < this.cantidadHormigas; hormiga++ ){
                
                this.lambda = (hormiga + 1)/this.cantidadHormigas;

                this.construirSolucion();       

                //this.imprimirSolucion();
                
                this.evaluarSolucion();

                
                //this.nuevoPunto.imprimirEvaluaciones();

                this.actualizarConjuntoPareto();
                
                this.actualizarFeromonas();
                /**/
            }
             

        }

        this.frentePareto.imprimirFrente();
    }

    private boolean condicionParada(){
    // -------------------------------------------------------------------------

    // -------------------------------------------------------------------------

        return( this.generacion > cantidadMaximaGeneraciones );
    }

    private boolean fueVisitado( int estadoJ ){
    // ------------------------------------------------------------------------

        int indice;

    // ------------------------------------------------------------------------

        for( indice=0; indice <= this.indiceActual; indice++ ){
            if( this.vectorActual[ indice ] == estadoJ ){
                return( true );
            }                
        }

        return( false );
    }

    private int obtenerSiguientePorMaximo(){
    // ----------------------------------------------------------------------

        int estadoI, estadoJ, vecino;
        double visibilidadUno, visibilidadDos   ,
                valorVecino, maximo;

    // ----------------------------------------------------------------------

        estadoI = this.vectorActual[ this.indiceActual ];

        estadoJ = MOACSQAP.NO_ACCESIBLE;

        maximo  = -MOACSQAP.INFINITO;

        for( vecino= 0; vecino < this.cantidadLocalidades; vecino++ ){
            if( !this.fueVisitado( vecino ) ){

                // en realidad, ya se eleva a las potencias correspondientes
                visibilidadUno  = this.mObjetivo1[ estadoI ][vecino]*this.mDistancias[this.indiceActual][this.indiceActual+1];
                visibilidadUno  = 1/visibilidadUno;
                visibilidadUno  = Math.pow( visibilidadUno, this.lambda*this.beta );

                visibilidadDos  = this.mObjetivo1[ estadoI ][vecino]*this.mDistancias[this.indiceActual][this.indiceActual+1];
                visibilidadDos  = 1/visibilidadDos;
                visibilidadDos  = Math.pow( visibilidadDos, ( 1 - this.lambda )*this.beta );

                valorVecino = this.feromanaT[ this.indiceActual ][ vecino ]*visibilidadUno*visibilidadDos;

                if( valorVecino > maximo ){
                    estadoJ = vecino;
                    maximo  = valorVecino;
                }
            }
        }

        return( estadoJ );
    }

    private double obtenerValorVecino( int estadoI, int vecino ){
    // ------------------------------------------------------------------------

        double valorVecino,
               visibilidadUno, visibilidadDos;

     // ------------------------------------------------------------------------

        // en realidad, ya se eleva a las potencias correspondientes
        visibilidadUno  = this.mObjetivo1[ estadoI ][vecino]*this.mDistancias[this.indiceActual][this.indiceActual+1];
        visibilidadUno  = 1/visibilidadUno;
        visibilidadUno  = Math.pow( visibilidadUno, this.lambda*this.beta );

        visibilidadDos  = this.mObjetivo1[ estadoI ][vecino]*this.mDistancias[this.indiceActual][this.indiceActual+1];
        visibilidadDos  = 1/visibilidadDos;
        visibilidadDos  = Math.pow( visibilidadDos, ( 1 - this.lambda )*this.beta );

        valorVecino = this.feromanaT[ this.indiceActual ][ vecino ]*visibilidadUno*visibilidadDos;

        return( valorVecino );
    }

    private int obtenerSiguientePorRuleta(){
    // ----------------------------------------------------------------------

        int estadoI, indice, vecino;

        double torta, valorVecino;

        double ruleta[][];

    // ----------------------------------------------------------------------

        ruleta                  = new double[2][this.cantidadLocalidades];

        estadoI                 = this.vectorActual[ this.indiceActual ];

        torta                   = 0;

        indice                  = 0;

        // Se construye la torta y registra el pedazo correspondiente
        // a cada vecino

        for( vecino=0; vecino < this.cantidadLocalidades; vecino++ ){

            if( !this.fueVisitado(vecino) ){
                
                valorVecino = this.obtenerValorVecino(estadoI, vecino);
                
                torta+= valorVecino;

                ruleta[ 0 ][ indice ] = valorVecino;
                ruleta[ 1 ][ indice ] = vecino;

                indice++;
            }
        }

        // Lanzamiento de la ruleta

        torta   = this.numerSeudoAleatorio.nextDouble()*torta;
        
        while( --indice >= 0 ){

            torta   = torta - ruleta[ 0 ][ indice ];

            if( torta < 0 )
                return( (int)ruleta[1][ indice ] );
        }

        return( MOACSQAP.NO_ACCESIBLE );
    }

    private int buscarSiguienteEstado(){
    // ------------------------------------------------------------------------

        double q;
        int estadoJ;
        
    // ------------------------------------------------------------------------


        q       = this.numerSeudoAleatorio.nextDouble();

        if( q < this.qInicial ){
            estadoJ = this.obtenerSiguientePorMaximo();
        }
        else{
            estadoJ = this.obtenerSiguientePorRuleta();
        }

        return( estadoJ );
    }

    private void construirSolucion(){
    // ------------------------------------------------------------------------

        int cantidadEstados ,
            estadoI         ,
            estadoJ         ,
            indice          ,
            vectorSolucion[];

        
    // ------------------------------------------------------------------------


        mDistancias     = this.intanciaProblema.obtenerMDistancias();
        mObjetivo1      = this.intanciaProblema.obtenerMObjetivoUno();
        mObjetivo2      = this.intanciaProblema.obtenerMObjetivoDos();

        estadoI         = this.servicioInicio;
        cantidadEstados = this.intanciaProblema.obtenerCantidadLocalidades();

        //vectorSolucion  = new int[ cantidadEstados ];

        this.indiceActual= 0;
        //vectorSolucion[ this.indiceActual ] = estadoI;
        this.vectorActual[ this.indiceActual ] = estadoI;


        while( indiceActual < ( cantidadEstados - 1 ) ){
            estadoJ = this.buscarSiguienteEstado();

            // Actualización paso a paso de feromonas
            this.tau                        = feromanaT[ this.indiceActual ][ estadoJ ];
            this.tau                        = ( 1 - this.rho )*this.tau + this.rho*this.tau;
            feromanaT[ this.indiceActual ][ estadoJ ] = this.tau;

            this.indiceActual++;

            this.vectorActual[ this.indiceActual ] = estadoJ;

            estadoI = this.vectorActual[ this.indiceActual ];
        }


    }

    private void evaluarSolucion(){
    // ------------------------------------------------------------------------

        int localidadI, localidadJ, servicioI, servicioJ;

        double distancia, resultadoObjetivoUno, resultadoObjetivoDos;

    // ------------------------------------------------------------------------

        this.nuevoPunto          = new Punto( 2 );

        resultadoObjetivoUno    = 0;
        resultadoObjetivoDos    = 0;

        for( localidadI=0; localidadI < this.cantidadLocalidades; localidadI++ ){
            servicioI   = this.vectorActual[ localidadI ];

            for( localidadJ=0; localidadJ < this.cantidadLocalidades; localidadJ++ ){

                if( localidadI != localidadJ ){
                    servicioJ   = this.vectorActual[ localidadJ ];

                    distancia   = this.mDistancias[ localidadI ][ localidadJ ];

                    resultadoObjetivoUno+= distancia*this.mObjetivo1[servicioI][servicioJ];

                    resultadoObjetivoDos+= distancia*this.mObjetivo2[servicioI][servicioJ];
                }

            }
            
        }

        this.nuevoPunto.asignarValorObjetivo( Punto.INDICE_OBJETIVO_UNO, resultadoObjetivoUno );

        this.nuevoPunto.asignarValorObjetivo( Punto.INDICE_OBJETIVO_DOS, resultadoObjetivoDos );
        
        //nuevoPunto.imprimirEvaluaciones();
    }

    private void inicializarMatrizFeromonas(){
    // ----------------------------------------------------------------------

        int fila, columna;

    // ----------------------------------------------------------------------
        
        for( fila=0; fila < cantidadLocalidades; fila++ ){
            for( columna=0; columna < cantidadLocalidades; columna++ ){
                this.feromanaT[ fila ][ columna ] = this.tInicial;
            }
        }
    }

    private void inicializarParametros(){
    // ----------------------------------------------------------------------

    // ----------------------------------------------------------------------
        

        this.cantidadHormigas   = 10;
        this.generacion         = 1;
        this.lambda             = 0; // Se inicializa dependiendo de la hormiga k/m
        this.beta               = 0.5;
        this.qInicial           = 0.6;
        this.rho                = 0.7;

        this.cantidadMaximaGeneraciones = 100;

        // ********************************************************************
        this.tInicial           = 0.0001;
        // ********************************************************************
        
        this.frentePareto       = new FrentePareto();
        
        this.intanciaProblema   = new Instancia();
            this.intanciaProblema.cargarInstanciaQAP( Instancia.ARCHIVO_QAP751_QAP );

        cantidadLocalidades        = this.intanciaProblema.obtenerCantidadLocalidades();

        this.feromanaT          = new double[ cantidadLocalidades ][ cantidadLocalidades ];
        this.vectorActual       = new int[ this.cantidadLocalidades ];


        this.numerSeudoAleatorio= new Random();
        this.servicioInicio     = (this.cantidadLocalidades - 1);
        this.servicioInicio     = (int)(this.servicioInicio*this.numerSeudoAleatorio.nextDouble());       
        
        this.inicializarMatrizFeromonas();
        
    }

    public void imprimirSolucion(){
    // ------------------------------------------------------------------------

        int indice;

    // ------------------------------------------------------------------------

        for( indice=0; indice < this.cantidadLocalidades; indice++ )
            System.out.print( this.vectorActual[ indice ] + "," );

        System.out.println( "" );
    }

    public static void main( String argv[] ){
    // ----------------------------------------------------------------------

        MOACSQAP moacs;

    // ----------------------------------------------------------------------

        moacs = new MOACSQAP();

        moacs.buscarConjuntoPareto();        
    }
}
